/*
* @Author: wanghongfucoder
* @Date:   2017-09-05 11:15:43
* @Last Modified by:   wanghongfucoder
* @Last Modified time: 2017-09-05 14:12:03
*/

import java.util.Queue;
import java.util.List;
import java.util.PriorityQueue;
import java.util.ArrayList;

public class Graph {

	//定点
	private List<Vertex> vertexs;

	//边
	private int[][] edges;

	private int[][] result;
	//没有访问的顶点
	private Queue<Vertex> unVisited;

	public Graph(List<Vertex> vertexs,int[][] edges){
		this.vertexs=vertexs;
		this.edges=edges;
		this.result=new int[edges.length][edges.length];
		intiUnVisited();
	}

	/**
	 * 搜索各顶点最短路径
	 */
	public void search(){

		while (!unVisited.isEmpty()){
			Vertex vertex=unVisited.element();
			vertex.setMarked(true);
			//获取所有未访问的邻居
			List<Vertex> neighbors=getNeighbors(vertex);
			//更新邻居的最短路径
            updatesDistance(vertex, neighbors);
			pop();
		}
		System.out.println("search over");
	}


	/**
	 * 更新所有邻居的最短路径
	 * @param vertex    [description]
	 * @param neighbors [description]
	 */
	public void updatesDistance(Vertex vertex,List<Vertex> neighbors){

		for(Vertex neighbor :neighbors){
			updateDistance(vertex,neighbor);
		}
	}

	/**
	 * 更新邻居的最短路径
	 * @param vertex   [description]
	 * @param neighbor [description]
	 */
	public  void updateDistance(Vertex vertex, Vertex  neighbor){

		int distance=getDistance(vertex,neighbor)+vertex.getPath();
		if (distance< neighbor.getPath()) {
			neighbor.setPath(distance);
		}
		int sourceIndex=vertexs.indexOf(vertex);
		int desIndex=vertexs.indexOf(neighbor);
		result[sourceIndex][desIndex]=neighbor.getPath();
		result[desIndex][sourceIndex]=neighbor.getPath();

	}


	/**
	 * 初始化未访问的顶点集合
	 */
	public void intiUnVisited(){
		unVisited=new PriorityQueue<Vertex>();
		for (Vertex v: vertexs) {
			unVisited.add(v);
		}
	}

	private void pop(){
		unVisited.poll();
	}

	/**
	 * 获取顶点到目标顶点的距离
	 * @param  source       [description]
	 * @param  destination  [description]
	 * @return              [description]
	 */
	private  int getDistance(Vertex source,Vertex destination){
		int sourceIndex=vertexs.indexOf(source);
		int desIndex=vertexs.indexOf(destination);
		return edges[sourceIndex][desIndex];
	}


	/**
	 * 获取顶点所有(未访问的)邻居
	 * @param  v [description]
	 * @return   [description]
	 */
	public List<Vertex> getNeighbors(Vertex v){
		List<Vertex> neighbors = new ArrayList<Vertex>();
		int position=vertexs.indexOf(v);
		Vertex neighbor=null;
		int distance;
		for (int i=0; i<vertexs.size();i++) {
			if (i==position) {
				//顶点本身，跳过
				continue;
			}
			distance=edges[position][i];
			if (distance<Integer.MAX_VALUE) {
				//是邻居(路径可达)
				neighbor=getVertex(i);
				if (!neighbor.isMarked()) {
					neighbors.add(neighbor);
				}
			}
		}
		return neighbors;
	}


	/**
	 * 根据顶点位置获取顶点
	 * @param  index [description]
	 * @return       [description]
	 */
	private Vertex getVertex(int index){
		return vertexs.get(index);
	}


	public  void printGraph(){
		int verNums=vertexs.size();
		for (int row=0; row<verNums; row++) {
			for (int col=0; col<verNums;col++) {
				if (Integer.MAX_VALUE==edges[row][col]) {
					System.out.print("X");
					System.out.print(" ");
					continue;
				}
				System.out.print(edges[row][col]);
				System.out.print(" ");
			}
			System.out.println();
		}
	}

	public  void printResult(){
		int verNums=vertexs.size();
		for (int row=0; row<verNums; row++) {
			for (int col=0; col<verNums;col++) {
				if (Integer.MAX_VALUE==result[row][col]) {
					System.out.print("X");
					System.out.print(" ");
					continue;
				}
				System.out.print(result[row][col]);
				System.out.print(" ");
			}
			System.out.println();
		}
	}
}